// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-27 13:51
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

public class JumpGreedy {
    // 通过局部最优解获取全局最优解
    // 找到最后一步，然后往回推
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int step = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if ((nums[i] + i) >= position) { // 首先找到最后一个可以直接到达尾部的节点，然后依次往后推
                    position = i;
                    ++step;
                    break;
                }
            }
        }
        return step;
    }
}
